//
// Created by Administrator on 2021/4/22.
//

/*
给你一个 m x n 的矩阵 matrix 和一个整数 k ，找出并返回矩阵内部矩形区域的不超过 k 的最大数值和。

题目数据保证总会存在一个数值和不超过 k 的矩形区域。


示例 1：
输入：matrix = [[1,0,1],[0,-2,3]], k = 2
输出：2
解释：蓝色边框圈出来的矩形区域[[0, 1], [-2, 3]]的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。

示例 2：
输入：matrix = [[2,2,-1]], k = 3
输出：3


来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/max-sum-of-rectangle-no-larger-than-k
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <vector>
#include <iostream>
#include <set>
#include <climits>

using namespace std;

class Solution { // 题解 做不出。。。
public:
    int maxSumSubmatrix(vector<vector<int>> &matrix, int k) {
        /**通过枚举上下边界确定矩形的上下边
         * 在确定上下边的区域内，计算各列的前缀和，将二维问题转换成一维问题
         * 等效于在一个递增数列中找到连续的n个数，和不大于k的最大值
         * **/
        int ans = INT_MIN; // 结果 初始化为最小值
        auto m = matrix.size(), n = matrix[0].size(); // 给定矩阵的长和宽
        for (int i = 0; i < m; ++i) { // 枚举上边界
            vector<int> sum(n);
            for (int j = i; j < m; ++j) { // 枚举下边界
                for (int c = 0; c < n; ++c) {
                    sum[c] += matrix[j][c]; // 更新每列的元素和
                }
                set<int> sumSet{0};
                int s = 0;
                for (int v : sum) {
                    /** 找到Sr-Sl <= k 的最大值
                     * Sl >= Sr-k
                     * 对于每一个前缀和的右端点，找到符合条件的最小Sl
                     * **/
                    s += v;  // 前缀和 枚举右侧
                    auto lb = sumSet.lower_bound(s - k); // lower_bound找到第一个大等于s-k的前缀和
                    if (lb != sumSet.end()) {
                        ans = max(ans, s - *lb); // 更新Sr-Sl
                    }
                    sumSet.insert(s); // 有序set添加前缀和
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> v{vector<int>{1, 0, 1}, vector<int>{0, -2, 3}};
    cout << sol.maxSumSubmatrix(v, 2) << endl;
    return 0;
}
